|
In mathematics, a Diophantine equation is an equation of the form ''P''(''x''1, ..., ''x''''j'', ''y''1, ..., ''y''''k'')=0 (usually abbreviated ''P''(',')=0 ) where ''P''(',') is a polynomial with integer coefficients. A Diophantine set is a subset ''S'' of Nj 〔 (Planet Math Definition )〕 so that for some Diophantine equation ''P''(',')=0. : That is, a parameter value is in the Diophantine set S if and only if the associated Diophantine equation is satisfiable under that parameter value. Note that the use of natural numbers both in ''S'' and the existential quantification merely reflects the usual applications in computability and model theory. We can equally well speak of Diophantine sets of integers and freely replace quantification over natural numbers with quantification over the integers.〔 The two definitions are equivalent. This can be proved using Lagrange's four-square theorem. 〕 Also it is sufficient to assume ''P'' is a polynomial over and multiply ''P'' by the appropriate denominators to yield integer coefficients. However, whether quantification over rationals can also be substituted for quantification over the integers it is a notoriously hard open problem. The MRDP theorem states that a set of integers is Diophantine if and only if it is computably enumerable.〔The theorem was established in 1970 by Matiyasevich and is thus also known as Matiyasevich's theorem. However, the proof given by Matiyasevich relied extensively on previous work on the problem and the mathematical community has moved to calling the equivalence result the MRDP theorem or the Matiyasevich-Robinson-Davis-Putnam theorem, a name which credits all the mathematicians that made significant contributions to this theorem.〕 A set of integers ''S'' is recursively enumerable if and only if there is an algorithm that, when given an integer, halts if that integer is a member of ''S'' and runs forever otherwise. This means that the concept of general Diophantine set, apparently belonging to number theory, can be taken rather in logical or recursion-theoretic terms. This is far from obvious, however, and represented the culmination of some decades of work. Matiyasevich's completion of the MRDP theorem settled Hilbert's tenth problem. Hilbert's tenth problem〔David Hilbert posed the problem in his celebrated list, from his 1900 address to the International Congress of Mathematicians.〕 was to find a general algorithm which can decide whether a given Diophantine equation has a solution among the integers. While Hilbert's tenth problem is not a formal mathematical statement as such the nearly universal acceptance of the (philosophical) identification of a decision algorithm with a total computable predicate allows us to use the MRDP theorem to conclude the tenth problem is unsolvable. ==Examples== The well known Pell equation : is an example of a Diophantine equation with a parameter. As has long been known, the equation has a solution in the unknowns precisely when the parameter is 0 or not a perfect square. In the present context, one says that this equation provides a ''Diophantine definition'' of the set : consisting of 0 and the natural numbers that are not perfect squares. Other examples of Diophantine definitions are as follows: * The equation only has solutions in when a is not a power of 2. * The equation only has solutions in when a is greater than 1 and is not a prime number. * The equation defines the set of pairs such that 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Diophantine set」の詳細全文を読む スポンサード リンク
|